//
// Created by id on 2025/10/08
//  @file myCharKMPNextVal.c
//  @desc 基于 myChar 类型实现 KMP 改进版算法（NextVal优化）
//        支持教材版本（1-based）和实际版本（0-based）
//  @author id
//  @date 2025-10-08
//  @version 1.0
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100  ///< myChar 最大容量

// ------------------------- 类型定义 -------------------------

/**
 * @struct myChar
 * @brief 自定义字符串类型
 *
 * - ch[MAX_SIZE] : 字符数组
 * - length       : 当前字符串长度
 *
 * @note 教材版本习惯使用 1-based 下标，实际版本使用 0-based 下标
 */
typedef struct myChar {
    char ch[MAX_SIZE];  ///< 字符数组
    int length;         ///< 当前长度
} myChar;

// ------------------------- NextVal 生成函数 -------------------------

/**
 * @brief 教材版本（1-based）改进版 nextVal 数组生成
 * @param pattern 模式串
 * @param nextVal 输出 nextVal 数组
 * @note
 *   - nextVal[i] 表示匹配失败时模式串回退位置
 *   - 教材版本下标从 1 开始
 */
void getNextValBase1(myChar *pattern, int nextVal[]) {
    if (pattern == NULL) {
        printf("pattern is NULL\n");
        return;
    }

    int i = 1;  // 当前计算 nextVal[i]
    int j = 0;  // 当前匹配前缀长度
    nextVal[1] = 0;  // 第1个字符没有前缀后缀

    while (i < pattern->length) {
        if (j == 0 || pattern->ch[i] == pattern->ch[j]) {
            i++;
            j++;
            if (pattern->ch[i] != pattern->ch[j]) {
                nextVal[i] = j;
            } else {
                nextVal[i] = nextVal[j]; // 避免重复比较
            }
        } else {
            j = nextVal[j]; // 回退
        }
    }
}

/**
 * @brief 实际版本（0-based）改进版 nextVal 数组生成
 * @param pattern 模式串
 * @param nextVal 输出 nextVal 数组
 * @note
 *   - nextVal[i] 表示匹配失败时模式串回退位置
 *   - 实际版本下标从 0 开始，更适合 C 数组操作
 */
void getNextValBase0(myChar *pattern, int nextVal[]) {
    if (pattern == NULL) {
        printf("pattern is NULL\n");
        return;
    }

    int i = 0;  // 当前计算 nextVal[i]
    int j = -1; // 当前匹配前缀长度
    nextVal[0] = -1;

    while (i < pattern->length - 1) {
        if (j == -1 || pattern->ch[i] == pattern->ch[j]) {
            i++;
            j++;
            if (pattern->ch[i] != pattern->ch[j]) {
                nextVal[i] = j;
            } else {
                nextVal[i] = nextVal[j]; // 避免重复比较
            }
        } else {
            j = nextVal[j]; // 回退
        }
    }
}

// ------------------------- 改进版 KMP 匹配函数 -------------------------

/**
 * @brief 教材版本 KMP 匹配（1-based）
 * @param text 主串
 * @param pattern 模式串
 * @param nextVal 模式串 nextVal 数组
 * @return 匹配位置（1-based），未匹配返回 -1
 */
int newIndexKMPBase1(myChar *text, myChar *pattern, int nextVal[]) {
    if (pattern == NULL || pattern->length == 0) return -1;
    if (pattern->length > text->length) return -1;

    int i = 1; // text 指针（1-based）
    int j = 1; // pattern 指针（1-based）

    getNextValBase1(pattern, nextVal);

    while (i <= text->length && j <= pattern->length) {
        if (j == 0 || text->ch[i] == pattern->ch[j]) {
            i++;
            j++;
        } else {
            j = nextVal[j]; // 回退模式串
        }
    }

    return (j > pattern->length) ? (i - pattern->length) : -1;
}

/**
 * @brief 实际版本 KMP 匹配（0-based）
 * @param text 主串
 * @param pattern 模式串
 * @param nextVal 模式串 nextVal 数组
 * @return 匹配位置（0-based），未匹配返回 -1
 */
int newIndexKMPBase0(myChar *text, myChar *pattern, int nextVal[]) {
    if (pattern == NULL || pattern->length == 0) return -1;
    if (pattern->length > text->length) return -1;

    int i = 0; // text 指针（0-based）
    int j = 0; // pattern 指针（0-based）

    getNextValBase0(pattern, nextVal);

    while (i < text->length && j < pattern->length) {
        if (j == -1 || text->ch[i] == pattern->ch[j]) {
            i++;
            j++;
        } else {
            j = nextVal[j]; // 回退模式串
        }
    }

    return (j == pattern->length) ? (i - pattern->length) : -1;
}

// ------------------------- 测试主函数 -------------------------

int main() {
    myChar text;
    myChar pattern;
    int nextVal[MAX_SIZE];

    // ---------------- Base1 初始化 ----------------
    char txt[] = "hello google";
    text.length = 12;
    for (int k = 1; k <= text.length; k++) {
        text.ch[k] = txt[k-1]; // Base1 索引
    }

    char pat[] = "google";
    pattern.length = 6;
    for (int k = 1; k <= pattern.length; k++) {
        pattern.ch[k] = pat[k-1]; // Base1 索引
    }

    // Base1 KMP 调用
    int indexBase1 = newIndexKMPBase1(&text, &pattern, nextVal);
    printf("---- Base1 KMP ----\n");
    if (indexBase1 != -1)
        printf("Pattern found at position (Base1): %d\n", indexBase1);
    else
        printf("Pattern not found (Base1)\n");

    printf("NextVal array (Base1):\n");
    for (int k = 1; k <= pattern.length; k++)
        printf("%d ", nextVal[k]);
    printf("\n\n");

    // ---------------- Base0 初始化 ----------------
    text.length = 12;
    for (int k = 0; k < text.length; k++)
        text.ch[k] = txt[k]; // Base0 索引

    pattern.length = 6;
    for (int k = 0; k < pattern.length; k++)
        pattern.ch[k] = pat[k]; // Base0 索引

    // Base0 KMP 调用
    int indexBase0 = newIndexKMPBase0(&text, &pattern, nextVal);
    printf("---- Base0 KMP ----\n");
    if (indexBase0 != -1)
        printf("Pattern found at position (Base0): %d\n", indexBase0);
    else
        printf("Pattern not found (Base0)\n");

    printf("NextVal array (Base0):\n");
    for (int k = 0; k < pattern.length; k++)
        printf("%d ", nextVal[k]);
    printf("\n");

    return 0;
}
